package LC;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * https://leetcode.com/problems/permutations/description/
 * Given a collection of distinct numbers, return all possible permutations.
 * For example,
 * [1,2,3] have the following permutations:
 * [
 * [1,2,3],
 * [1,3,2],
 * [2,1,3],
 * [2,3,1],
 * [3,1,2],
 * [3,2,1]
 * ]
 */
public class LC_047_PermutationsII_DFS_Perm {
    public static void main(String[] args) {
        int[] a = {1, 2, 3};
        List<List<Integer>> res = Solution.permuteUnique(a);
        System.out.println(res);
    }

    public static class Solution {
        static List<List<Integer>> permuteUnique(int[] nums) {
            List<List<Integer>> res = new LinkedList<>();
            List<Integer> tmpList = new LinkedList<>();
            boolean[] visited = new boolean[nums.length];

            Arrays.sort(nums);
            dfs(nums, res, tmpList, visited);
            return res;
        }

        private static void dfs(int[] nums, List<List<Integer>> res, List<Integer> item, boolean[] visited) {
            int length = nums.length;

            if (item.size() == length) {
                res.add(new LinkedList<>(item));
                return;
            }

            for (int i = 0; i < length; i++) {
                while (i > 0 && i < length && nums[i] == nums[i - 1] && !visited[i - 1])
                    i++;
                if (i == length)
                    return;

                if (visited[i])
                    continue;

                item.add(nums[i]);
                visited[i] = true;

                dfs(nums, res, item, visited);

                visited[i] = false;
                item.remove(item.size() - 1);
            }
        }
    }
}
